﻿//https://ac.nowcoder.com/acm/problem/50039
//算法思路：
//简单的排列组合问题，结果等于 n 与 m 个 n - 1 的乘积。
//C++ 算法代码：
#include <iostream>
using namespace std;

const int MOD = 109;
int main()
{
	int n, m;
	cin >> n >> m;
	int ret = n;
	for (int i = 0; i < m - 1; i++)
	{
		ret = ret * (n - 1) % MOD;
	}

	cout << ret << endl;

	return 0;
}

//https://www.nowcoder.com/practice/e88b41dc6e764b2893bc4221777ffe64?tpId=308&tqId=40477&ru=/exam/oj
//算法思路：
//简单 bfs 应⽤题。
//C++ 算法代码：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
int x1, y1, x2, y2;

char arr[N][N];
int dist[N][N]; // [i, j] 位置是否已经搜索过，以及到达 [i, j] 位置的最短距离
int bfs()
{
	if (arr[x2][y2] == '*') return -1;

	memset(dist, -1, sizeof dist); // 表⽰还没开始搜索
	queue<pair<int, int>> q;
	q.push({ x1, y1 });
	dist[x1][y1] = 0;
	while (q.size())
	{
		auto [a, b] = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x = a + dx[i], y = b + dy[i];
			if (x >= 1 && x <= n && y >= 0 && y <= m && arr[x][y] == '.' &&
				dist[x][y] == -1)
			{
				q.push({ x, y });
				dist[x][y] = dist[a][b] + 1;
				if (x == x2 && y == y2) return dist[x2][y2];
			}
		}
	}
	return -1;
}
int main()
{
	cin >> n >> m >> x1 >> y1 >> x2 >> y2;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
		}
	}
	cout << bfs() << endl;
	return 0;
}


//https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=196&tqId=37562&ru=/exam/oj
//主持⼈调度（⼆）（贪⼼ + 优先级队列）

//算法思路：
//左端点排序，然后搞个堆：
//a.先把第⼀个区间的右端点加⼊到堆中；
//b.遍历后⾯的区间，分情况讨论：
//		i.如果左端点⼤于等于堆顶元素，能接在后⾯，⼲掉堆顶，然后把这个区间的右端点加⼊堆；
//		ii.否则的话，只能再来⼀个⼈，只把这个区间的右端点加⼊堆。
//c.最后堆的⼤⼩就是需要的⼈数。
class Solution
{
public:
	int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
	{
		sort(startEnd.begin(), startEnd.end());
		priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
		heap.push(startEnd[0][1]); // 先把第⼀个区间放进去
		for (int i = 1; i < n; i++) // 处理剩下的区间
		{
			int a = startEnd[i][0], b = startEnd[i][1];
			if (a >= heap.top()) // 没有重叠

			{
			heap.pop();
			heap.push(b);
			}
			else // 有重叠
			{
				heap.push(b); // 重新安排⼀个⼈
			}
		}
		return heap.size();
	}
};